package sort;

public class QuickSort implements Sort {
    @Override
    public void sort(int[] arr, boolean asc) {
        sort(arr, 0, arr.length - 1, asc);
    }

    private void sort(int[] arr, int begin, int end, boolean asc) {
        if (begin >= end) {
            return;
        }

        int last = arr[end], left = begin, right = end;
        while (left < right) {
            while (left < right && ((asc && arr[left] < last) || (!asc && arr[left] > last))){
                left++;
            }
            arr[right] = arr[left];
            while (left < right && ((asc && arr[right] > last) || (!asc && arr[right] < last))) {
                right--;
            }
            arr[left] = arr[right];
        }
        arr[left] = last;
        sort(arr, begin, left - 1, asc);
        sort(arr, left + 1, end, asc);
    }
}
